package com.chapter5.string;

import com.chapter1.basic.queue.Queue;

/**
 * 
 * @ClassName: TrieST
 * @Description: R向单词查找树
 * 
 *               node数组索引对应单词中的某个字母，如果很多很长的单词，就会产生大量空数组
 * 
 * @author minjun
 * @date 2015年3月21日 下午11:35:07
 * 
 * @param <Value>
 */
public class TrieST<Value> implements StringST<Value> {

	private static final int R = 256;

	// 初始化根节点，将所有的单词都放在这个已经存在了的根节点的子数组中
	private Node root = new Node();

	private static class Node {
		private Object value;
		private Node[] next = new Node[R];

		/**
		 * 
		 * @Title: hasNoNullLink
		 * @Description: 是否拥有非空link
		 * @param @return 设定文件
		 * @return boolean 返回类型
		 * @throws
		 */
		public boolean hasNoNullLink() {
			for (Node n : next) {
				if (n != null)
					return true;
			}
			return false;
		}
	}

	@Override
	public void put(String key, Value value) {
		root = put(key, value, root, 0);
	}

	/**
	 * 
	 * @Title: put
	 * @Description: 递归向树中添加元素
	 * @param @param key
	 * @param @param value
	 * @param @param node
	 * @param @param d
	 * @param @return 设定文件
	 * @return Node 返回类型
	 * @throws
	 */
	private Node put(String key, Value value, Node node, int d) {
		if (node == null) {
			node = new Node();
		}

		if (d == key.length()) {
			node.value = value;
			return node;
		}
		node.next[key.charAt(d)] = put(key, value, node.next[key.charAt(d)],
				d + 1);
		return node;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Value get(String key) {
		Node node = get(key, root, 0);
		if (node == null)
			return null;
		return (Value) node.value;
	}

	private Node get(String key, Node node, int d) {
		if (node == null)
			return null;
		if (d == key.length()) {
			return node;
		}
		// 继续向下查找
		return get(key, node.next[key.charAt(d)], d + 1);
	}

	@Override
	public void delete(String key) {
		root = delete(key, root, 0);
	}

	private Node delete(String key, Node node, int d) {
		if (node == null) {
			return null;
		}
		if (d == key.length()) {
			node.value = null;
		} else {
			char a = key.charAt(d);
			node.next[a] = delete(key, node.next[a], d + 1);
		}
		if (node.value == null && !node.hasNoNullLink()) {
			return null;
		}
		return node;
	}

	@Override
	public boolean contains(String key) {
		return get(key) != null;
	}

	@Override
	public boolean isEmpty() {
		return false;
	}

	@Override
	public int size() {
		return 0;
	}

	@Override
	public Iterable<String> keys() {
		Queue<String> q = new Queue<String>();
		keys(root, q, "");
		return q;
	}

	/**
	 * 
	 * @Title: keys
	 * @Description: 优化之后的实现版本
	 * @param @param node
	 * @param @param q
	 * @param @param s 设定文件
	 * @return void 返回类型
	 * @throws
	 */
	private void keys(Node node, Queue<String> q, String s) {
		if (node == null)
			return;
		if (node.value != null) {
			q.offer(s);
		} else {
			for (int i = 0; i < node.next.length; i++) {
				keys(node.next[i], q, s + (char) i);
			}
		}
	}

	/**
	 * bad implemention
	 */
	// private void keys(Node node, Queue<String> q,String c) {
	// for(int i=0;i<node.next.length;i++){
	// if(node.next[i]!=null){
	// if(node.next[i].value!=null){
	// q.offer(c+(char)i);
	// }else{
	// keys(node.next[i], q,c+(char)i);
	// }
	// }
	// }
	// }

	// keysWithPrefix方法较差的实现方式，这样会首先没必要的迭代出所有的keys，然后在做一道筛选过程
	// Queue<String> q=new Queue<String>();
	// Iterable<String> keys=keys();
	// for(String key:keys){
	// if(key.startsWith(s)){
	// q.offer(key);
	// }
	// }

	/**
	 * 应用：如搜索引擎的自动补全提示
	 */
	@Override
	public Iterable<String> keysWithPrefix(String s) {
		Queue<String> q = new Queue<String>();
		Node node = get(s, root, 0);
		keys(node, q, s);
		return q;
	}

	@Override
	public Iterable<String> keysThatMatch(String s) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * ip地址路由选择算法--查找最接近的ip地址
	 */
	@Override
	public String longestPrefixOf(String s) {
		int len = longestPrefixOf(s, root, 0, 0);
		return s.substring(0, len);
	}

	private int longestPrefixOf(String s, Node node, int d, int len) {
		//如果后面没有元素了，直接返回已经记录了的长度
		if (node == null)
			return len;
		//碰到一个有值的节点就记录一个
		if (node.value != null)
			len = d;
		//到达最大长度之后就不在继续，否则会产生索引溢出
		if (d == s.length())
			return len;
		return longestPrefixOf(s, node.next[s.charAt(d)], d + 1, len);
	}

}
